package com.zl.learning.arithmetic.leetcode;

import org.junit.Test;

public class TestKMP {
    private static final String mastStr = "abcdefwwwabfcefg";

    public static void main(String[] args) {
        boolean flag = mastStr.contains("abf");
        System.out.println(flag);
        /**
         abcdefghijklmn
         abcfab
         */
    }

    @Test
    public void test1() {
        String mastStr = "abcaabbabcaabccfsabcdabcffff";
        String str = "abcaabcc";
//        int[] a = getNext(str);
//        System.out.println(Arrays.toString(str.toCharArray()));
//        System.out.println(Arrays.toString(a));
        int index = kmp(mastStr, str);
        System.out.println(index);
        System.out.println(mastStr.substring(index, index + str.length()).equals(str));
    }

    private int[] getNext(String t) {
        int i = 0, j = -1;
        int[] next = new int[t.length() + 1];
        next[0] = -1;
        while (i < t.length()) {
            if (j == -1 || t.charAt(i) == t.charAt(j)) {
                ++i;
                ++j;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

    int kmp(String s, String t) {
        int i = 0, j = 0;
        int[] next = getNext(t);
        while (i < s.length() && j < t.length()) {
            if (j == -1 || s.charAt(i) == t.charAt(j)) {
                i++;
                j++;
            } else {
                j = next[j];               //j回退。。。
            }
        }
        if (j >= t.length()) {
            return (i - t.length());         //匹配成功，返回子串的位置
        } else {
            return (-1);                  //没找到
        }
    }
}
